from typing import List


class Solution:
    def dfs(self, u, ans, path, n, col, dg, udg):
        if u == n:
            ans.append(path)
            return
        for i in range(n):
            if not col[i] and not dg[u - i + n] and not udg[i + u]:
                path[u][i] = 'Q'
                col[i], dg[u - i + n], udg[i + u] = True, True, True
                self.dfs(u + 1, ans, path, n, col, dg, udg)
                col[i], dg[u - i + n], udg[i + u] = False, False, False
                path[u][i] = '.'

    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        path = [str(['.' for i in range(n)]) for i in range(n)]
        col, dg, udg = [False for i in range(n)], [False for i in range(2*n)], [False for i in range(2*n)]
        self.dfs(0, ans, path, n, col, dg, udg)
        return ans

Solution().solveNQueens()